package 图;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. 岛屿数量
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * 核心思路：对于每个遇到的'1'，递归地把相邻的四个方向的'1'都置为'0'。这样递归完成后，
 * 整个岛屿都被处理过了。比如，当前坐标是(i,j)，那么递归处理i+1,j；i-1,j；i,j+1；i,j-1这四个方向，当然要确保这些坐标在网格范围内。
 *
 * 解题思路：
 *  要解决岛屿数量的问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历并标记相连的陆地。核心思想是遍历整个网格，
 *  当遇到一块陆地时，通过搜索将所有相连的陆地标记为已访问，从而将整个岛屿计入一次。具体步骤如下：
 *     1、遍历网格：逐个访问网格中的每个元素。
 *     2、发现陆地：当遇到值为 '1' 的元素时，表示发现了一个新岛屿，计数加一。
 *     3、标记并扩展：使用 DFS 或 BFS 将当前陆地及其所有相连的陆地标记为已访问（如置为 '0'），避免重复计数。
 *  可以采用深度优先（DFS）的思路， 递归当前节点的上下左右，直到遇到边界或者遇到值为 '0' 的元素，这时可以统计出一个岛屿。
 *  时间复杂度：O(m * n)，其中 m 和 n 分别为行数和列数。
 *
 *  我们也可以用广度优先BFS的思路，但是比起BFS，DFS深度优先更容易理解和实现。
 */
public class L_200 {

    /**
     * DFS：递归地将所有相邻陆地标记为 '0'，从而将整个岛屿“淹没”。每次遇到新的陆地时，计数器加一。
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0){
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 如果当前节点为陆地，则开始递归统计岛屿
                if (grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++; // 岛屿数量+1
                }
            }
        }
        return count;
    }

    /**
     * 递归实现,统计出一个岛屿的函数
     * @param grid
     * @param i
     * @param j
     */
    private void dfs(char[][] grid, int i, int j){
        // 如果坐标越界或者当前位置不是陆地，则直接返回
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        // 已经统计过的陆地标记为0，避免重复统计
        grid[i][j] = '0';
        // 递归处理上下左右四个方向的陆地
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }


    /**
     * BFS实现, 采用队列辅助完成
     * BFS：使用队列迭代处理相邻陆地，确保所有相连的陆地都被标记。每次从队列中取出一个位置，检查其四个方向，将未访问的陆地加入队列并标记。
     * @param grid
     * @return
     */
    public int numIslandsBFS(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0'; // 标记为已访问
                    queue.offer(new int[]{i, j});
                    count++;
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        for (int[] dir : directions) {
                            int x = curr[0] + dir[0];
                            int y = curr[1] + dir[1];
                            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {
                                grid[x][y] = '0';
                                queue.offer(new int[]{x, y});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}
